/*
 * CS181 Darts game
 */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

/* 
 * Parameters of a dartboard.
 * NUM_WEDGES is simply the number of different wedges around the board.
 * WEDGES is the list of wedges, in counter-clockwise order, beginning
 * with the rightmost edge (angle 0).
 */

/* The standard dartboard
#define NUM_WEDGES 20
#define WEDGES { 6, 13, 4, 18, 1, 20, 5, 12, 9, 14, 11, 8, 16, 7, 19, 3, 17, 2, 15, 10 }
#define START_SCORE 301 */

/* The medium-size dartboard */
 #define NUM_WEDGES 8
 #define WEDGES { 4, 6, 2, 7, 1, 8, 3, 5 }
 #define START_SCORE 100 

/* A much smaller dartboard 
#define NUM_WEDGES 4
#define WEDGES { 1, 4, 2, 3 }
#define START_SCORE 9*/

/* The number of distinct actions, or targets, on the dartboard */
#define NUM_ACTIONS (6 * NUM_WEDGES)

/* <CODE HERE>: You will need to define the number of states and start state. */
#define NUM_STATES START_SCORE+1
#define START_STATE START_SCORE

/* The epoch size used to update the optimal policy in the model-based algorithm */
#define EPOCH_SIZE 10

/* 
 * Two arrays for describing a dartboard.
 * The wedges array converts a position around the dartboard into a wedge number.
 * Positions are numbered from 0, starting at the rightmost position, and
 * move counter-clockwise.  Thus, in the standard dartboard, 6 is in position 0,
 * 13 is in position 1 and so on.
 * The angles array is the inverse of the wedges array.  For each wedge number, 
 * from 1 to NUM_WEDGES, it gives the angle of the wedge.  The angle needs to be scaled 
 * by 2 Pi / NUM_WEDGES to convert into radians.
 *
 * The contents of the wedges array is described in the WEDGES constant.
 */
int wedges[NUM_WEDGES];
int angles[NUM_WEDGES + 1];

/* The epsilon value used to determine convergence of the value iteration algorithm. */
#define EPSILON .001

/* The default discount factor used in the infinite value iteration algorithm. 
 * You will want to vary this parameter in your experiments.
 */
#define GAMMA 0.5


/* 
 * A location on a dartboard consists of the wedge number and ring.
 * Wedges are numbered from 1 to NUM_WEDGES. Rings are as follows.
 */
typedef enum ring { 
  CENTER,       /* double bullseye (center of the board) worth 2.5 * NUM_WEDGES     */
  INNER_RING,   /* inner ring                            worth 1.25 * NUM_WEDGES    */
  FIRST_PATCH,  /* area between inner and middle rings   worth the wedge number     */
  MIDDLE_RING,  /* middle ring                           worth 3 * the wedge number */
  SECOND_PATCH, /* area between middle and outer rings   worth the wedge number     */
  OUTER_RING,   /* outer ring                            worth 2 * the wedge number */
  MISS          /* off the board                         worth nothing              */
} ring;

/* The data structure used to specify an action, or target, on the dartboard. */
typedef struct {
  ring ring;
  int wedge;
} location;


/* --------- FUNCTIONS IN DARTS.C --------- */

/* 
 * init_board should be called at the beginning of the program to initialize
 * the angles array.
 */
void init_board();

/* Store all possible actions in the given array */
void get_actions(location *actions);

/* <CODE HERE>: Given a state, specify the reward to be used in the value iteration 
 * algorithm. Returns 0 for all states by default. 
 */
float R(int s, location a);

/* Determine the raw score for hitting a specific dartboard location. */
int location_to_score(location loc);

/*
 * The play function plays a single game.  
 * It resets the score to START_SCORE, and calls start_game to get an action.
 * It then completes that action (i.e. throws at the target) and keeps track of the score.
 * It will keep calling get_target until the score reaches zero.
 * Returns the number of turns taken.
 */
int play();

/* Plays n games of darts and returns the average number of turns to completion over n games. */
void test(int n);

/* <CODE HERE>: You will need to edit this function to run your experiments. */
int main(int argc, char **argv);

/* --------- RELEVANT FUNCTIONS IN THROW.C --------- */

/* 
 * A throw takes as argument an action to complete (a target), 
 * and returns the result of that throw.
 * The result is produced stochastically using the throwing model.
 */
location throw(location a);
  
/*
 * Question 2 of the problem set refers to a relatively simple, known throwing model.
 * Call use_simple_thrower to use this model.
 */
void use_simple_thrower();

/*
 * Initialize a relatively complex throwing model.  The model will be used for all
 * subsequent throws, until initialized again.  The throwing model
 * is randomly generated using the current random seed. Question 4 requires the use
 * of such a model.
 */
void init_thrower();

/* --------- FUNCTIONS IN MDP.C --------- */

/* Get the inital action to be completed, as specified by the optimal policy. */
location start_game(float gamma); 

/* Return the next action to be completed, given the current state. */
location get_target(int s);

/* 
 * <CODE HERE>: Given a current state, next state, and action, return the probability
 * of transitioning from the current to next state by taking that action. Returns 0 
 * for all input by default. 
 */
float T(int s, int s_prime, location a);

/* Run the infinite value iteration algorithm to determine the optimal policy. */
void infinite_value_iteration(float);

/* --------- FUNCTIONS IN MODELBASED.C and MODELFREE.C --------- */

/* 
 * <CODE HERE>: Exploration/ exploitation strategy one.
 */
//int ex_strategy_one();
int ex_strategy_one(int t);

/* 
 * <CODE HERE>: Exploration/ exploitation strategy two.
 */
//int ex_strategy_two();
int ex_strategy_two(int t, float *num_actions_in_state);

/* --------- FUNCTIONS IN MODELFREE.C --------- */

/* 
 * <CODE HERE>: You will need to code this file from scratch.
 */
void Q_learning(float gamma, int num_games);

/* --------- FUNCTIONS IN MODELBASED.C --------- */

/* Run the infinite value iteration algorithm to determine the optimal policy given the learned transition function. */
void modelbased_value_iteration(float gamma, float T_matrix[][NUM_STATES][NUM_ACTIONS], int *pi_star); 

/* Learn the transition model using model-based reinforcement learning. */
void modelbased(float gamma, int epoch_size, float T_matrix[][NUM_STATES][NUM_ACTIONS], int num_games);
